// 1. 生成斐波那契数列的第n项
// O(N)
// function getFibArr (num: number): number {
//     const fibArr = [0, 1];
//     while (fibArr.length < num) {
//         const len = fibArr.length;
//         const next = fibArr[len - 2] + fibArr[len - 1]; // 前两项生成下一项
//         fibArr.push(next);
//     }
//     return fibArr[num - 1];
// }

// function getFibArr1 (num: number): number {
//     if (num < 2) {
//         return num;
//     }
//     return getFibArr1(num - 2) + getFibArr1(num - 1);
// }

// console.time('循环');
// getFibArr(40);
// console.timeEnd('循环');

// console.time('递归');
// getFibArr1(40);
// console.timeEnd('递归');

// 2.
// const numArr = [
//     'a',
//     { a: 1, b: 'hello' },
//     ['a', 2, [3, 4], { c: 50, d: [6, 7] }],
//     8,
// ];

// function getMax (arr: any): number {
//     let max = -Infinity;
//     for (const key in arr) {
//         const item = arr[key];
//         switch (typeof item) {
//             case 'number':
//                 // 拿item和max相比
//                 if (max < item) {
//                     max = item;
//                 }
//                 break;
//             case 'object':
//                 // 拿临时的结果和max相比
//                 const tmpMax = getMax(item);
//                 if (max < tmpMax) {
//                     max = tmpMax;
//                 }
//                 break;
        
//             default:
//                 break;
//         }
//     }
//     return max;
// }

// console.log(getMax(numArr));

// 3. 
// const arr1 = [
//     'a',
//     { a: 1, b: 'hello' },
//     ['a', 2, [3, 4], { c: 5, d: [6, 7] }],
//     8,
// ];

// deep深度  clone克隆
// function deepClone (obj: object | any[] | null): object | any[] {
//     if (!obj) {
//         return obj;
//     }
//     const result = Array.isArray(obj) ? [] : {};
//     for (const key in obj) {
//         const item = obj[key];
//         switch (typeof item) {
//             case 'object':
//                 // 引用数据类型的情况
//                 result[key] = deepClone(item);
//                 break;
        
//             default:
//                 // 基础数据类型的情况
//                 result[key] = item;
//                 break;
//         }
//     }
//     return result;
// }

// function deepClone1 (obj: object | any[] | null): object | any[] {
//     return JSON.parse( JSON.stringify(obj) );
// }

// // 封装测试性能的函数
function p (name, cb, count) {
    console.time(name);
    for (let i = 0; i < count; i++) {
        cb();
    }
    console.timeEnd(name);
}

// p('递归', () => {
//     deepClone(arr1);
// }, 10000);

// p('序列化', () => {
//     deepClone1(arr1);
// }, 10000);

// 4.
const nums = [0,0,1,1,1,2,2,3,3,4]; // i:3  

// O(N)
function unique1 (nums: number[]): number {
    if (nums.length === 0) {
        return 0;
    }
    let i = 1;
    while (nums[i] !== undefined) {
        const current = nums[i];
        const prev = nums[i - 1];
        if (current === prev) {
            nums.splice(i, 1);
        } else {
            i++;
        }
    }
    return nums.length;
}

// O(N)
function unique2 (nums: number[]): number {
    const newNums = Array.from(new Set(nums));
    nums.length = newNums.length;
    for (let i = 0; i < newNums.length; i++) {
        nums[i] = newNums[i];
    }
    return nums.length;
}

// O(N)
function unique3 (nums: number[]): number {
    if(nums.length === 0) {
        return 0;
    }
    let flagIndex = 0; // 目标索引
    let flag = nums[0]; // 目标
    for(let i = 1; i < nums.length; i++) {
        if(nums[i] !== flag){
            const j = ++flagIndex;
            nums[j] = nums[i]
            flag = nums[flagIndex]
        }
    }
    return flagIndex + 1
}

p('我的垃圾', () => {
    unique1(nums);
}, 1000000);

p('我的', () => {
    unique2(nums);
}, 1000000);

p('别人家', () => {
    unique3(nums);
}, 1000000);